package leetcode.f1t100;

/**
 * O(n)时间复杂度, O(1)空间复杂度, 找出缺失的最小正整数
 * https://leetcode.com/problems/first-missing-positive/
 * @Author lichongxiao
 * @Date 2022/9/27 15:21
 */
public class Q41_FirstMissingPositive {

    /**
     * O(n)Space O(n)time
     * @param nums
     * @return
     */
    public static int firstMissingPositive(int[] nums) {
        int length = nums.length;
        int[] store = new int[length];
        for(int i = 0;i<length;i++){
            if(nums[i]>0 && nums[i]<=length){
                store[nums[i]-1] = nums[i];
            }
        }
        for(int i = 0;i<length;i++){
            if(store[i] != i+1){
                return i+1;
            }
        }
        return length+1;
    }

    /**
     * O(1)Space O(n)time
     * @param nums
     * @return
     */
    public static int firstMissingPositive_1(int[] nums) {
        int length = nums.length;
        int swapT;
        for(int i = 0;i<length;){
            if(nums[i]>0 && nums[i]<=length && nums[nums[i]-1] != nums[i] ){
                swapT = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = swapT;
            } else {
                i++;
            }
        }
        for(int i = 0;i<length;i++){
            if(nums[i] != i+1){
                return i+1;
            }
        }
        return length+1;
    }


    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{2,1,4}));
    }
}
